61. Rotate List

Medium

Given a linked list, rotate the list to the right by k places, where k is non-negative.

Example 1:

Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

Example 2:

Input: 0->1->2->NULL, k = 4
Output: 2->0->1->NULL
Explanation:
rotate 1 steps to the right: 2->0->1->NULL
rotate 2 steps to the right: 1->2->0->NULL
rotate 3 steps to the right: 0->1->2->NULL
rotate 4 steps to the right: 2->0->1->NULL

1. 使用start每次记录linked list的开头，用while语句每次寻找linked list的尾部前一个数（不找尾部是因为linked list只知道next node，所以在尾部时，我们不知道尾部的上一个node是什么），然后target，即尾部node，是我们移动的目标，改变其指向到linked list开头，然后cur 指向None（cur变成尾部node了），最后更新start pointer指向新的开头，即target。重复上述步骤k次。

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next: 
            return head
        start = ListNode(None)
        start.next = head  # using start to record the head of linked list
        for _ in range(k):
            cur = start.next
            
            while cur.next.next:  # using this part to find the previous node of end node
                cur = cur.next
                
            # the end node, which is also the target we want to pop to the head
            target = cur.next 
            
            cur.next = None # the previous should be the new end node
            target.next = start.next # old end node will be the head of list
            start.next = target # renew the start pointer
        
        return start.next # return the linked list, exclude start pointer

很明显，算法的时间复杂度是O(k*n) n is the length of linked list. 乍看之下不算高，但是遇到k很大的情况肯定会超时，而且很明显有可以提升速度的地方。比如while语句寻找end node。

所以不如先遍历一遍知道linked list长度，然后k 用长度取模（k>length 会多转一圈）。然后cur遍历到需要cut的位置，cut后面的linked list block要被放到最前面。

class Solution:
    def rotateRight(self, head: ListNode, k: int) -> ListNode:
        if not head or not head.next: return head
        if not k : return head 
    
        # first we need know the length of linked list
        cur = head
        length = 0
        while cur:
            length += 1
            cur = cur.next
            
        k = k % length # simplify k
        if not k : return head
        
        cur = head # here cur was used to get the the previous node of NewHead
        for _ in range(length - k - 1): # reach to the cut position
            cur = cur.next
        
        newHead = cur.next # after cut is the linked list block which should be placed on in front
        cur.next = None # the node before cut will be the new end
        
        cur = newHead # here cur was used to get the end node of linked list block
        while(cur.next):
            cur = cur.next
        cur.next = head # link old head with linked list block
        

        return newHead # return the new head

O(2n) n is the length of linked list